#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

// 二维坐标上点的结构体定义
typedef struct Point
{
    double x;
    double y;
}Point;

//平面上任意两点对之间的距离计算公式
double distance(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

//自定义排序规则：依照结构体中的x成员变量升序排序
bool compareX(Point a, Point b)
{
    return a.x < b.x;
}

//自定义排序规则：依照结构体中的x成员变量升序排序
bool compareY(Point a, Point b)
{
    return a.y < b.y;
}

// 蛮力法求最近点对记录，并将两点记录再a、b中
double ClosestPair1(Point points[], int length, Point& a, Point& b)
{
    double minDist = DBL_MAX;     //初始距离为double型数据的最大值

    for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            double d = distance(points[i], points[j]);
            if (d < minDist)
            {
                minDist = d;
                a = points[i];
                b = points[j];
            }
        }
    }
    return minDist;
}

// 分治法求最近点对距离，并将两点记录再a、b中
double ClosestPair2(Point points[], int length, Point& a, Point& b)
{
    double minDist;     //记录集合points中最近两点距离

    if (length < 2)         //若子集长度小于2，返回为最大距离，表示不可达
    {
        return DBL_MAX;
    }
    else if (length == 2)       //若子集长度等于2，直接返回该两点的距离
    {
        a = points[0];
        b = points[1];
        minDist = distance(points[0], points[1]);
    }
    else      //子集长度大于3，进行分治求解
    {
        int i = 0, j = 0, k = 0, r = 0;    //用于控制for循环的循环变量
        //开辟两个存储排序后points左和右的子集
        Point* pTmp1 = new Point[length];
        Point* pTmp2 = new Point[length];

        sort(points, points + length, compareX);    //调用algorithm库中的sort函数对points进行排序，compareX为自定义的排序规则
        double mid = points[(length - 1) / 2].x;    //排完序后的中间下标值，即中位数

        for (i = 0; i < length / 2; i++)
        {
            pTmp1[i] = points[i];
        }
        for (j = 0, i = length / 2; i < length; i++, j++)
        {
            pTmp2[j] = points[i];
        }

        Point a1, b1, a2, b2;              //保存分割后两个子集中最小点对
        double d1, d2;                     //记录分割后两个子集中各自最小点对距离
        d1 = ClosestPair2(pTmp1, length / 2, a1, b1);             //分治求解左半部分子集的最近点  
        d2 = ClosestPair2(pTmp2, length - length / 2, a2, b2);    //分治求解右半部分子集的最近点  

        //记录最近点，最近距离
        if (d1 < d2)
        {
            minDist = d1;
            a = a1;
            b = b1;
        }
        else
        {
            minDist = d2;
            a = a2;
            b = b2;
        }

        //merge - 进行子集合解合并
        //求解跨分割线并在δ×2δ区间内的最近点对
        Point* pTmp3 = new Point[length];

        for (i = 0, k = 0; i < length; i++)          //取得中线2δ宽度的所有点对共k个
        {
            if (abs(points[i].x - mid) <= minDist)
            {
                pTmp3[k++] = points[i];
            }
        }

        sort(pTmp3, pTmp3 + k, compareY);       // 以y排序矩形阵内的点集合

        for (i = 0; i < k; i++)
        {
            if (pTmp3[j].x - mid >= 0)      // 只判断左侧部分的点
            {
                continue;
            }
            r = 0;
            for (j = i + 1; j <= i + 6 + r && j < k; j++)    //只需与有序的领接的的6个点进行比较
            {
                //  假如i点是位于mid左边则只需判断在mid右边的j点即可
                if (pTmp3[j].x - mid < 0)
                {
                    r++;
                    continue;
                }
                //如果跨分割线的两点距离小于已知最小距离，则记录该距离和两点
                if (distance(pTmp3[i], pTmp3[j]) < minDist)
                {
                    minDist = distance(pTmp3[i], pTmp3[j]);
                    a = pTmp3[i];
                    b = pTmp3[j];
                }
            }
        }
    }
    return minDist;
}

int main()
{
    int num;

    cout << "请输入点对个数：";
    cin >> num;
    if (num < 2)
    {
        cout << "请输入大于等于2的点个数！！" << endl;
    }
    else
    {
        Point a, b;            //最近点对
        double distance;       //点对距离
        Point* points = new Point[num];      //点对存储数组
        for (int i = 0; i < num; i++)
        {
            cout << "请输入第" << i + 1 << "对点：";
            cin >> points[i].x >> points[i].y;
        }

        distance = ClosestPair1(points, num, a, b);
        cout << endl << "蛮力法求最近点对为：" << "(" << a.x << "," << a.y << ")和" << "(" << b.x << "," << b.y << ")" << endl;
        cout << "最近点对距离为：" << distance << endl;

        distance = ClosestPair2(points, num, a, b);
        cout << endl << "分治法求最近点对为：" << "(" << a.x << "," << a.y << ")和" << "(" << b.x << "," << b.y << ")" << endl;
        cout<< "最近点对距离为：" << distance << endl;
    }
    system("pause");
    return 0;
}